home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 March / macformat-022.iso / Shareware City / Developers / MA3.1.1 & CW4.5 / Modifications / *OR* replace these files / ObjectHeap.cp next >
Encoding:
Text File  |  1994-09-17  |  16.4 KB  |  532 lines  |  [TEXT/MPS ]
  1. /*
  2. *    This file has been changed from the original MacApp 3.1.1
  3. *    to support the metrowerks CodeWarrior compilers C/C++ 1.1.1.
  4. *    These changes are known *not* to work with earlier versions
  5. *    of CodeWarrior.  Every attempt though has been made to to keep 
  6. *    this file compatible with other development environments.
  7. *
  8. *    Mark Anderson
  9. *    metrowerks
  10. *    9/16/94
  11. *
  12. */
  13.  
  14. // ObjectHeap.cp 
  15. // Copyright © 1985-1994 by Apple Computer, Inc.  All rights reserved.
  16.  
  17. #ifndef PLATFORMMEMORY_H
  18. #include <PlatformMemory.h>
  19. #endif
  20.  
  21. #ifndef __OBJECTHEAP__
  22. #include <ObjectHeap.h>
  23. #endif
  24.  
  25.  
  26. //========================================================================================
  27. // CLASS ChunkyBlock
  28. //========================================================================================
  29. #pragma segment Main
  30.  
  31. //----------------------------------------------------------------------------------------
  32. // ChunkyBlock::ChunkyBlock
  33. //----------------------------------------------------------------------------------------
  34.  
  35. ChunkyBlock::ChunkyBlock()
  36. {
  37.     SetBlockType(kBlockTypeId);
  38.     SetMagicNumber(kMagicNumber);
  39.     fNext = NULL;
  40. }
  41.  
  42. //----------------------------------------------------------------------------------------
  43. // ChunkyBlock::ChunkyBlock
  44. //----------------------------------------------------------------------------------------
  45.  
  46. ChunkyBlock::ChunkyBlock(unsigned int sizeIndex,
  47.                                  unsigned int blockIndex)
  48. {
  49.     SetSizeIndex(sizeIndex);
  50.     SetBlockIndex(blockIndex);
  51.     SetBlockType(kBlockTypeId);
  52.     SetMagicNumber(kMagicNumber);
  53.     fNext = NULL;
  54. }
  55.  
  56. //----------------------------------------------------------------------------------------
  57. // ChunkyBlock::GetChunk
  58. //----------------------------------------------------------------------------------------
  59.  
  60. Chunk* ChunkyBlock::GetChunk(FW_BlockSize blkSize)
  61. {
  62.     Chunk *chk 
  63.         = (Chunk *) ((FW_BytePtr) this - sizeof(SChunkHeader) - blkSize * GetBlockIndex());
  64.     return chk;
  65. }
  66.  
  67. //----------------------------------------------------------------------------------------
  68. // ChunkyBlock::IsBusy
  69. //----------------------------------------------------------------------------------------
  70.  
  71. Boolean ChunkyBlock::IsBusy(FW_BlockSize blockSize)
  72. {
  73.     return this->GetChunk(blockSize)->IsBlockBusy(GetBlockIndex());
  74. }
  75.  
  76. //----------------------------------------------------------------------------------------
  77. // ChunkyBlock::SetBusy
  78. //----------------------------------------------------------------------------------------
  79.  
  80. void ChunkyBlock::SetBusy(FW_BlockSize blockSize, Boolean busy)
  81. {
  82.     this->GetChunk(blockSize)->SetBlockBusy(GetBlockIndex(), busy);
  83. }
  84.  
  85.  
  86. //========================================================================================
  87. // Chunk
  88. //========================================================================================
  89.  
  90. //----------------------------------------------------------------------------------------
  91. // Chunk::Chunk
  92. //----------------------------------------------------------------------------------------
  93. #pragma segment HeapSeg
  94.  
  95. Chunk::Chunk(short blocksPerChunk,
  96.                      unsigned int sizeIndex,
  97.                      FW_BlockSize blockSize)
  98. {
  99.     fHeader.fBlockBusyBits = 0;
  100.     void* blkPtr = (void *) ((FW_BytePtr) this + sizeof(SChunkHeader));
  101.     for (unsigned int i = 0; i < blocksPerChunk; i++)
  102.     {
  103.         ChunkyBlock *blk = new(blkPtr)ChunkyBlock(sizeIndex, i);
  104.         blkPtr = (void *) ((FW_BytePtr) blkPtr + blockSize);
  105.     }
  106. }
  107.  
  108. //----------------------------------------------------------------------------------------
  109. // Chunk::IsBlockBusy
  110. //----------------------------------------------------------------------------------------
  111. #pragma segment HeapSeg
  112.  
  113. Boolean Chunk::IsBlockBusy(unsigned int whichBlock)
  114. {
  115.     unsigned short mask = 0x0001 << whichBlock;
  116.  
  117.     return (fHeader.fBlockBusyBits & mask) != 0;
  118. }
  119.  
  120. //----------------------------------------------------------------------------------------
  121. // Chunk::SetBlockBusy
  122. //----------------------------------------------------------------------------------------
  123.  
  124. void Chunk::SetBlockBusy(unsigned int whichBlock, Boolean busy)
  125. {
  126.     unsigned short mask = 0x0001 << whichBlock;
  127.  
  128.     if (busy)
  129.         fHeader.fBlockBusyBits |= mask;
  130.     else
  131.         fHeader.fBlockBusyBits &= ~mask;
  132. }
  133.  
  134. //----------------------------------------------------------------------------------------
  135. // Chunk::GetBlock
  136. //----------------------------------------------------------------------------------------
  137.  
  138. ChunkyBlock* Chunk::GetBlock(unsigned int blkIndex, FW_BlockSize blkSize)
  139. {
  140.     ChunkyBlock * blk 
  141.         = (ChunkyBlock *) ((FW_BytePtr) this + sizeof(SChunkHeader) + blkIndex * blkSize);
  142.     return blk;
  143. }
  144.  
  145.  
  146. //========================================================================================
  147. // ObjectHeap
  148. //========================================================================================
  149.  
  150. const FW_BlockSize ObjectHeap::kDefaultBlockSizes[] = {sizeof(ChunkyBlock), 10, 14, 18, 0};
  151.  
  152. //----------------------------------------------------------------------------------------
  153. // ObjectHeap::ObjectHeap
  154. //----------------------------------------------------------------------------------------
  155. #pragma segment HeapSeg
  156.  
  157. ObjectHeap::ObjectHeap(unsigned long initialSize,
  158.                    unsigned long incrementSize,
  159.                    short blocksPerChunk) :
  160.     BestFitHeap(initialSize, incrementSize),
  161.     fBlockSizes(kDefaultBlockSizes)
  162. {
  163. #ifdef DEBUG
  164.     CompilerCheck();
  165. #endif
  166.  
  167.     fBlocksPerChunk = blocksPerChunk;
  168.  
  169.     for (fNumberOfBlockSizes = 0; fBlockSizes[fNumberOfBlockSizes]; fNumberOfBlockSizes++)
  170.         ;
  171. }
  172.  
  173. //----------------------------------------------------------------------------------------
  174. // ObjectHeap::ObjectHeap
  175. //----------------------------------------------------------------------------------------
  176. #pragma segment HeapSeg
  177.  
  178. ObjectHeap::ObjectHeap(const FW_BlockSize* blockSizes,
  179.                    unsigned long initialSize,
  180.                    unsigned long incrementSize,
  181.                    short blocksPerChunk) :
  182.     BestFitHeap(initialSize, incrementSize),
  183.     fBlockSizes(blockSizes)
  184. {
  185. #ifdef DEBUG
  186.     CompilerCheck();
  187. #endif
  188.  
  189.     fBlocksPerChunk = blocksPerChunk;
  190.  
  191.     for (fNumberOfBlockSizes = 0; fBlockSizes[fNumberOfBlockSizes]; fNumberOfBlockSizes++)
  192.         ;
  193. }
  194.  
  195. //----------------------------------------------------------------------------------------
  196. // ObjectHeap::IObjectHeap
  197. //----------------------------------------------------------------------------------------
  198. #pragma segment HeapSeg
  199.  
  200. void ObjectHeap::IObjectHeap()
  201. {
  202.     this->IBestFitHeap();
  203. }
  204.  
  205. //----------------------------------------------------------------------------------------
  206. // ObjectHeap::~ObjectHeap
  207. //----------------------------------------------------------------------------------------
  208. #pragma segment HeapSeg
  209.  
  210. ObjectHeap::~ObjectHeap()
  211. {
  212. }
  213.  
  214. //----------------------------------------------------------------------------------------
  215. // ObjectHeap::DoAllocate
  216. //----------------------------------------------------------------------------------------
  217. #pragma segment HeapSeg
  218.  
  219. void* ObjectHeap::DoAllocate(FW_BlockSize size, FW_BlockSize& allocatedSize)
  220. {
  221.     if (size + ChunkyBlock::kBusyOverhead > fBlockSizes[fNumberOfBlockSizes - 1])
  222.         return BestFitHeap::DoAllocate(size, allocatedSize);
  223.     else
  224.     {
  225.         unsigned int sizeIndex = this->SizeIndex(size);
  226.         allocatedSize = fBlockSizes[sizeIndex] - ChunkyBlock::kBusyOverhead;
  227.         return this->AllocateBlock(sizeIndex);
  228.     }
  229. }
  230.  
  231. //----------------------------------------------------------------------------------------
  232. // ObjectHeap::DoBlockSize
  233. //----------------------------------------------------------------------------------------
  234. #pragma segment HeapSeg
  235.  
  236. FW_BlockSize ObjectHeap::DoBlockSize(const void* ptr) const
  237. {
  238.     ChunkyBlock *block
  239.         = (ChunkyBlock *) ((FW_BytePtr) ptr - ChunkyBlock::kBusyOverhead);
  240.         
  241.     if (block->GetBlockType() == BestFitBlock::kBlockTypeId)
  242.         return BestFitHeap::DoBlockSize(ptr);
  243.     else
  244.         return fBlockSizes[block->GetSizeIndex()] - ChunkyBlock::kBusyOverhead;
  245. }
  246.  
  247. //----------------------------------------------------------------------------------------
  248. // ObjectHeap::DoFree
  249. //----------------------------------------------------------------------------------------
  250. #pragma segment HeapSeg
  251.  
  252. void ObjectHeap::DoFree(void* ptr)
  253. {
  254.     ChunkyBlock *block 
  255.         = (ChunkyBlock *) ((FW_BytePtr) ptr - ChunkyBlock::kBusyOverhead);
  256.         
  257.     if (block->GetBlockType() == BestFitBlock::kBlockTypeId)
  258.         BestFitHeap::DoFree(ptr);
  259.     else
  260.         this->FreeBlock(block);
  261. }
  262.  
  263. #ifdef DEBUG
  264. //----------------------------------------------------------------------------------------
  265. // ObjectHeap::DoIsValidBlock
  266. //----------------------------------------------------------------------------------------
  267. #pragma segment HeapSeg
  268.  
  269. Boolean ObjectHeap::DoIsValidBlock(void* ptr) const
  270. {
  271.     Boolean isBlockValid = false;
  272.     
  273.     ChunkyBlock *block
  274.         = (ChunkyBlock *) ((FW_BytePtr) ptr - ChunkyBlock::kBusyOverhead);
  275.  
  276.     if (block->GetBlockType() == BestFitBlock::kBlockTypeId)
  277.         isBlockValid = BestFitHeap::DoIsValidBlock(ptr);
  278.     else
  279.         isBlockValid
  280.             = block->GetSizeIndex() <= fNumberOfBlockSizes &&
  281.               block->GetBlockIndex() <= fBlocksPerChunk &&
  282.               block->GetMagicNumber() == (unsigned int) ChunkyBlock::kMagicNumber;
  283.  
  284.     return isBlockValid;
  285. }
  286. #endif
  287.  
  288. //----------------------------------------------------------------------------------------
  289. // ObjectHeap::DoReset
  290. //----------------------------------------------------------------------------------------
  291. #pragma segment HeapSeg
  292.  
  293. void ObjectHeap::DoReset()
  294. {
  295.     ChunkyBlockStack clr;
  296.  
  297.     for (int i = 0; i < fNumberOfBlockSizes; i++)
  298.         fFreeLists[i] = clr;
  299.  
  300.     BestFitHeap::DoReset();
  301. }
  302.  
  303. //----------------------------------------------------------------------------------------
  304. // ObjectHeap::AllocateBlock
  305. //----------------------------------------------------------------------------------------
  306. #pragma segment HeapSeg
  307.  
  308. void *ObjectHeap::AllocateBlock(unsigned int sizeIndex)
  309. {
  310.     if (fFreeLists[sizeIndex].Top() == NULL)
  311.         this->CreateNewChunk(sizeIndex);
  312.  
  313.     ChunkyBlock * blk = fFreeLists[sizeIndex].Pop();
  314.     if (blk != NULL)
  315.     {
  316.         blk->SetBusy(fBlockSizes[sizeIndex], true);
  317.         return (void *) ((FW_BytePtr) blk + ChunkyBlock::kBusyOverhead);
  318.     }
  319.     else
  320.         return NULL;
  321. }
  322.  
  323. //----------------------------------------------------------------------------------------
  324. // ObjectHeap::CreateNewChunk
  325. //----------------------------------------------------------------------------------------
  326. #pragma segment HeapSeg
  327.  
  328. void ObjectHeap::CreateNewChunk(unsigned int sizeIndex)
  329. {
  330.     FW_BlockSize allocatedSize;
  331.     FW_BlockSize allocSize = sizeof(SChunkHeader) + fBlocksPerChunk * fBlockSizes[sizeIndex];
  332.     Chunk * chk = new(BestFitHeap::DoAllocate(allocSize, allocatedSize))Chunk(fBlocksPerChunk, sizeIndex, fBlockSizes[sizeIndex]);
  333.     if (chk != NULL)
  334.     {
  335.         for (unsigned int i = 0; i < fBlocksPerChunk; i++)
  336.         {
  337.             ChunkyBlock * blk = chk->GetBlock(i, fBlockSizes[sizeIndex]);
  338.             blk->SetBusy(fBlockSizes[sizeIndex], false);
  339.             fFreeLists[sizeIndex].Push(blk);
  340.         }
  341.     }
  342. }
  343.  
  344. //----------------------------------------------------------------------------------------
  345. // ObjectHeap::FreeBlock
  346. //----------------------------------------------------------------------------------------
  347. #pragma segment HeapSeg
  348.  
  349. void ObjectHeap::FreeBlock(ChunkyBlock* blk)
  350. {
  351.     blk->SetBusy(fBlockSizes[blk->GetSizeIndex()], false);
  352.     fFreeLists[blk->GetSizeIndex()].Push(blk);
  353.  
  354.     // Check to see if all blocks in this block's Chunk are free, if so then free the
  355.     // Chunk.
  356.  
  357.     Chunk *chk = blk->GetChunk(fBlockSizes[blk->GetSizeIndex()]);
  358.     if (!chk->IsBusy())
  359.     {
  360.         // Remove blocks in this Chunk from the free list. This is the achililles hill
  361.         // of the Heap. Its difficult to remove blocks from a singly linked list
  362.         // rapidly.
  363.  
  364.         void *begAddr = chk;
  365.         void *endAddr = (void *) ((FW_BytePtr) chk + 
  366.                                     sizeof(SChunkHeader) +
  367.                                     fBlocksPerChunk * fBlockSizes[chk->GetSizeIndex()]);
  368.         fFreeLists[chk->GetSizeIndex()].RemoveRange(begAddr, endAddr);
  369.         BestFitHeap::DoFree(chk);
  370.     }
  371. }
  372.  
  373. //----------------------------------------------------------------------------------------
  374. // ObjectHeap::SizeIndex
  375. //----------------------------------------------------------------------------------------
  376. #pragma segment HeapSeg
  377.  
  378. unsigned int ObjectHeap::SizeIndex(FW_BlockSize size)
  379. {
  380.     for (unsigned int i = 0; i < fNumberOfBlockSizes; i++)
  381.         if (size + ChunkyBlock::kBusyOverhead <= fBlockSizes[i])
  382.             return i;
  383.  
  384.     // Uh oh! An internal error:
  385.     
  386.     PLATFORM_DEBUGGER_STRING("Internal error in ObjectHeap::SizeIndex");
  387.     
  388.     return 0xFFFFFFFF;    // the former way of handling the internal error
  389.                         // we leave it in to defeat an xlC warning
  390. }
  391.  
  392. #ifdef DEBUG
  393. //----------------------------------------------------------------------------------------
  394. // ObjectHeap::CompilerCheck
  395. //----------------------------------------------------------------------------------------
  396. #pragma segment HeapSeg
  397.  
  398. void ObjectHeap::CompilerCheck()
  399. {
  400.     BestFitHeap::CompilerCheck();
  401.     
  402.     ChunkyBlock block;
  403.     
  404.     block.SetSizeIndex(0xF);
  405.     block.SetBlockIndex(0xE);
  406.     block.SetBlockType(ChunkyBlock::kBlockTypeId);
  407.     block.SetMagicNumber(0xC);
  408.     
  409.     PLATFORM_ASSERT(block.GetSizeIndex() == 0xF);
  410.     PLATFORM_ASSERT(block.GetBlockIndex() == 0xE);
  411.     PLATFORM_ASSERT(block.GetBlockType() == ChunkyBlock::kBlockTypeId);
  412.     PLATFORM_ASSERT(block.GetBlockType() != BestFitBlock::kBlockTypeId);
  413.     PLATFORM_ASSERT(block.GetMagicNumber() == 0xC);
  414.     
  415.     block.SetSizeIndex(0x7);
  416.     block.SetBlockIndex(0x6);
  417.     block.SetBlockType(BestFitBlock::kBlockTypeId);
  418.     block.SetMagicNumber(0x4);
  419.     
  420.     PLATFORM_ASSERT(block.GetSizeIndex() == 0x7);
  421.     PLATFORM_ASSERT(block.GetBlockIndex() == 0x6);
  422.     PLATFORM_ASSERT(block.GetBlockType() == BestFitBlock::kBlockTypeId);
  423.     PLATFORM_ASSERT(block.GetBlockType() != ChunkyBlock::kBlockTypeId);
  424.     PLATFORM_ASSERT(block.GetMagicNumber() == 0x4);
  425. }
  426. #endif
  427.  
  428. //========================================================================================
  429. // ChunkyBlockStack
  430. //========================================================================================
  431.  
  432. //----------------------------------------------------------------------------------------
  433. // ChunkyBlockStack::ChunkyBlockStack
  434. //----------------------------------------------------------------------------------------
  435. #pragma segment HeapSeg
  436.  
  437. ChunkyBlockStack::ChunkyBlockStack()
  438. {
  439.     fHead.SetNext(NULL);
  440. }
  441.  
  442. //----------------------------------------------------------------------------------------
  443. // ChunkyBlockStack::ChunkyBlockStack
  444. //----------------------------------------------------------------------------------------
  445. #pragma segment HeapSeg
  446.  
  447. ChunkyBlockStack::ChunkyBlockStack(const ChunkyBlockStack& blk) :
  448.     fHead(blk.fHead)
  449. {
  450. }
  451.  
  452. //----------------------------------------------------------------------------------------
  453. // ChunkyBlockStack::operator=
  454. //----------------------------------------------------------------------------------------
  455. #pragma segment HeapSeg
  456.  
  457. ChunkyBlockStack& ChunkyBlockStack::operator=(const ChunkyBlockStack& blk)
  458. {
  459.     fHead = blk.fHead;
  460.     return *this;
  461. }
  462.  
  463. //----------------------------------------------------------------------------------------
  464. // ChunkyBlockStack::Pop
  465. //----------------------------------------------------------------------------------------
  466. #pragma segment HeapSeg
  467.  
  468. ChunkyBlock* ChunkyBlockStack::Pop()
  469. {
  470.     ChunkyBlock * blk = fHead.GetNext();
  471.     fHead.SetNext(blk->GetNext());
  472.     return blk;
  473. }
  474.  
  475. //----------------------------------------------------------------------------------------
  476. // ChunkyBlockStack::Push
  477. //----------------------------------------------------------------------------------------
  478. #pragma segment HeapSeg
  479.  
  480. void ChunkyBlockStack::Push(ChunkyBlock* blk)
  481. {
  482.     blk->SetNext(fHead.GetNext());
  483.     fHead.SetNext(blk);
  484. }
  485.  
  486. //----------------------------------------------------------------------------------------
  487. // ChunkyBlockStack::RemoveRange
  488. //----------------------------------------------------------------------------------------
  489. #pragma segment HeapSeg
  490.  
  491. void ChunkyBlockStack::RemoveRange(void *begAddr, void *endAddr)
  492. {
  493.     ChunkyBlock *prevBlk = &fHead;
  494.     ChunkyBlock *curBlk = fHead.GetNext();
  495.  
  496.     while (curBlk != NULL)
  497.     {
  498.         void *curAddr = curBlk;
  499.  
  500.         if (curAddr >= begAddr && curAddr <= endAddr)
  501.         {
  502.             prevBlk->SetNext(curBlk->GetNext());
  503.             curBlk = curBlk->GetNext();
  504.         }
  505.         else
  506.         {
  507.             prevBlk = curBlk;
  508.             curBlk = curBlk->GetNext();
  509.         }
  510.     }
  511. }
  512.  
  513. //----------------------------------------------------------------------------------------
  514. // ChunkyBlockStack::Top
  515. //----------------------------------------------------------------------------------------
  516. #pragma segment HeapSeg
  517.  
  518. ChunkyBlock* ChunkyBlockStack::Top()
  519. {
  520.     return fHead.GetNext();
  521. }
  522.  
  523. //----------------------------------------------------------------------------------------
  524. // ChunkyBlockStack::~ChunkyBlockStack
  525. //----------------------------------------------------------------------------------------
  526. #pragma segment HeapSeg
  527.  
  528. ChunkyBlockStack::~ChunkyBlockStack()
  529. {
  530. }
  531.  
  532.